A map service can provide maps to one or more computing devices. The maps can include points of interest (POIs). A POI can be a place that is designated as useful or of interest to any user or all users. For example, a POI can be a shop, restaurant, or a hotel. Each POI may have an address (for example, a street address). To display a POI in a map, the map service can geocode the POI by associating a location (for example, latitude and longitude coordinates) with the POI. The online map service can display a marker representing the POI on the map at the latitude and longitude coordinates. The inverse technique, reverse geocoding, attempts to determine a POI to which a given latitude and longitude refers.